(******************************************************************************)
(**)                        ОТДЕЛ Игра; 
(******************************************************************************)
(* НАЗНАЧЕНИЕ: алгоритм игры "Крестики-нолики"                                *)
(* ПРАВИЛА:                                                                   *)
(*   Игра идёт на квадратном поле 3х3 клетки. Игроки по очереди ставят        *)
(*   в клетках — один крестики (+), второй нолики (о). Выигрывает тот,        *)
(*   кто первым замкнул линию (вертикальную, горизонтальную или диагональную).*)
(******************************************************************************)

ВИД  
  Позиция=ЦЕПЬ[10];  

ПЕР                  (*         номера клеток в позиции: |0 1 2| *)
  позиция-:Позиция;  (* текущая игровая позиция          |3 4 5| *)
  опозиция:Позиция;  (* текущий лучший ход машины        |6 7 8| *)

(******************************************************************************)
ЗАДАЧА ЕстьЛинияИз(зн:ЗНАК):КЛЮЧ;  
(* Цель:  поиск замкнутой линии в текущей позиции
 * До:    <зн> — вид искомых значков ('+' или 'о')
 * Ответ: ВКЛ, если в <позиция> есть линия из 3-х <зн> *)
УКАЗ 
  ЕСЛИ (позиция[0] = зн) И (позиция[1] = зн) И (позиция[2] = зн) ИЛИ 
       (позиция[3] = зн) И (позиция[4] = зн) И (позиция[5] = зн) ИЛИ 
       (позиция[6] = зн) И (позиция[7] = зн) И (позиция[8] = зн) ИЛИ 
       (позиция[0] = зн) И (позиция[3] = зн) И (позиция[6] = зн) ИЛИ 
       (позиция[1] = зн) И (позиция[4] = зн) И (позиция[7] = зн) ИЛИ 
       (позиция[2] = зн) И (позиция[5] = зн) И (позиция[8] = зн) ИЛИ 
       (позиция[0] = зн) И (позиция[4] = зн) И (позиция[8] = зн) ИЛИ 
       (позиция[6] = зн) И (позиция[4] = зн) И (позиция[2] = зн)
  ТО
    ВОЗВРАТ ВКЛ
  ИНАЧЕ
    ВОЗВРАТ ОТКЛ
  КОН
КОН ЕстьЛинияИз;  

(******************************************************************************)
ЗАДАЧА Окончена-():КЛЮЧ;  
(* Цель:  определить конец игры
 * Ответ: ВКЛ, если достигнут конец игры *)
ПЕР 
  n:ЦЕЛ;  
УКАЗ 
  ЕСЛИ ЕстьЛинияИз("+") ИЛИ ЕстьЛинияИз("о") ТО
    ВОЗВРАТ ВКЛ 
  КОН;  
  (* если еще можно ходить, то это не конец *)
  ОТ n:=0 ДО 8 ВЫП 
    ЕСЛИ позиция[n] = " " ТО
      ВОЗВРАТ ОТКЛ 
    КОН 
  КОН;  
  (* ничья *)
  ВОЗВРАТ ВКЛ 
КОН Окончена;  
  
(******************************************************************************)
ЗАДАЧА Оценить(свои:ЗНАК;  alpha,beta,глубина:ЦЕЛ):ЦЕЛ;  
(* Цель:  просчет наилучшего хода методом Alpha-beta отсечения
 * До:    <свои>    — свои значки
 *        < alpha > — нижняя оценка
 *        < beta >  — верхняя оценка
 *        <глубина> — глубина поиска
 * Ответ: оценка <позиция> с точки зрения <свои> *)
ПЕР 
  чужие:ЗНАК;  
  оценка:ЦЕЛ;  
  естьХод:КЛЮЧ; 
  n:ЦЕЛ;  
УКАЗ 
  ЕСЛИ свои = "о" ТО
    чужие:="+"
  ИНАЧЕ
    чужие:="о"
  КОН;  
  ЕСЛИ ЕстьЛинияИз(чужие) ТО  
    (* это наш проигрыш *) 
    ВОЗВРАТ -1
  КОН;  
  (* пока не нашли ни одной свободной клетки *)
  естьХод:=ОТКЛ; 
  (* переберём все клетки позиции *)
  ОТ n:=0 ДО 8 ВЫП 
    ЕСЛИ позиция[n] = " " ТО  
      естьХод:=ВКЛ; 
      (* сделаем ход *) 
      позиция[n]:=свои;  
      (* и оценим его *) 
      оценка:=-Оценить(чужие,-beta,-alpha,глубина+1);  
      ЕСЛИ оценка > alpha ТО 
        alpha:=оценка;  
        ЕСЛИ глубина = 0 ТО 
          опозиция:=позиция
        КОН 
      КОН;  
      (* восстановим позицию *)
      позиция[n]:=" ";  
      (* отсечение *)
      ЕСЛИ alpha >= beta ТО 
        ВОЗВРАТ alpha
      КОН 
    КОН 
  КОН;  
  ЕСЛИ естьХод ТО
    ВОЗВРАТ alpha
  ИНАЧЕ
    (* ничья *)
    ВОЗВРАТ 0
  КОН
КОН Оценить;  
  
(******************************************************************************)
ЗАДАЧА Ход-(n:ЦЕЛ); 
(* Цель:  полуход "+" и ответный полуход "о"
 * До:    < n >     — куда ходят "+" 
 * После: <позиция> — новая позиция  *)
ПЕР
  оценка:ЦЕЛ; 
УКАЗ
  позиция[n]:="+";  
  ЕСЛИ НЕ Окончена() ТО  
    оценка:=Оценить("о",-2,2,0);  
    позиция:=опозиция 
  КОН 
КОН Ход; 

(******************************************************************************)
ЗАДАЧА НачатьЗаново-; 
(* Цель:  подготовиться к новой игре *)
УКАЗ
  позиция:="         "
КОН НачатьЗаново; 

КОН Игра. 

▲ Вопросы, замечания и предложения высылайте на atimopheyev@yahoo.com или Издателю Глагола: